package com.yqx.guli.algorithm;

import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;

/**
 * leetcode  算法思想
 * 双指针
 * Leetcode 题解 - 双指针
 * 1. 有序数组的 Two Sum
 * 2. 两数平方和
 * 3. 反转字符串中的元音字符
 * 4. 回文字符串
 * 5. 归并两个有序数组
 * 6. 判断链表是否存在环
 * 7. 最长子序列
 * 双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。
 */
public class TwoPointers {

    /**
     * 167. Two Sum II - Input array is sorted (Easy)
     * <p>
     * Leetcode / 力扣
     * <p>
     * Input: numbers={2, 7, 11, 15}, target=9
     * Output: index1=1, index2=2
     * 题目描述：在有序数组中找出两个数，使它们的和为 target。
     * <p>
     * 解析：
     * 使用双指针，一个指针指向值较小的元素，一个指针指向值较大的元素。指向较小元素的指针从头向尾遍历，指向较大元素的指针从尾向头遍历。
     * <p>
     * 如果两个指针指向元素的和 sum == target，那么得到要求的结果；
     * 如果 sum > target，移动较大的元素，使 sum 变小一些；
     * 如果 sum < target，移动较小的元素，使 sum 变大一些。
     * 数组中的元素最多遍历一次，时间复杂度为 O(N)。只使用了两个额外变量，空间复杂度为 O(1)。
     */
    public int[] twoSum(int[] numbers, int target) {
        int[] retInt = new int[2];
        if (numbers == null) {
            return null;
        }
        int i = 0;
        int j = numbers.length - 1;
        while (i < j) {
            int sum = numbers[i] + numbers[j];
            if (sum == target) {
                return new int[]{i + 1, j + 1};
            }
            if (sum > target) {
                j--;
            } else {
                i++;
            }
        }
        return retInt;
    }


    /**
     * 633. Sum of Square Numbers (Easy)
     * Leetcode / 力扣
     * Input: 5
     * Output: True
     * Explanation: 1 * 1 + 2 * 2 = 5
     * 题目描述：判断一个非负整数是否为两个整数的平方和。
     * <p>
     * 可以看成是在元素为 0~target 的有序数组中查找两个数，使得这两个数的平方和为 target，如果能找到，则返回 true，表示 target 是两个整数的平方和。
     * 本题和 167. Two Sum II - Input array is sorted 类似，只有一个明显区别：一个是和为 target，一个是平方和为 target。本题同样可以使用双指针得到两个数，使其平方和为 target。
     * 本题的关键是右指针的初始化，实现剪枝，从而降低时间复杂度。设右指针为 x，左指针固定为 0，为了使 02 + x2 的值尽可能接近 target，我们可以将 x 取为 sqrt(target)。
     * 因为最多只需要遍历一次 0~sqrt(target)，所以时间复杂度为 O(sqrt(target))。又因为只使用了两个额外的变量，因此空间复杂度为 O(1)。
     *
     * @param target
     * @return
     */
    public boolean judgeSquareSum(int target) {
        if (target < 0) {
            return false;
        }
        int i = 0;
        int j = (int) Math.sqrt(target);
        while (i <= j) {
            int sum = i * i + j * j;
            if (sum == target) {
                System.out.println(target + " = " + i + "*" + i + " + " + j + "*" + j);
                return true;
            }
            if (sum > target) {
                j--;
            } else {
                i++;
            }
        }
        return false;
    }

    /**
     * 345. Reverse Vowels of a String (Easy)
     * Leetcode / 力扣
     * Given s = "leetcode", return "leotcede".
     * <p>
     * 使用双指针，一个指针从头向尾遍历，一个指针从尾到头遍历，当两个指针都遍历到元音字符时，交换这两个元音字符。
     * 为了快速判断一个字符是不是元音字符，我们将全部元音字符添加到集合 HashSet 中，从而以 O(1) 的时间复杂度进行该操作。
     * 时间复杂度为 O(N)：只需要遍历所有元素一次
     * 空间复杂度 O(1)：只需要使用两个额外变量
     */
    private final static HashSet<Character> vowels = new HashSet<>(
            Arrays.asList('a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'));

    public String reverseVowels(String s) {
        byte[] bytes = s.getBytes();
        int i = 0;
        int j = bytes.length - 1;
        StringBuilder sb = new StringBuilder();
        byte[] newBytes = new byte[bytes.length];
        while (i <= j) {
            byte a = bytes[i];
            byte b = bytes[j];
            char aa = s.charAt(i);
//            System.out.println(aa);
            char bb = s.charAt(j);
//            System.out.println(bb);
            if (!vowels.contains(aa)) {
                newBytes[i] = a;
                i++;
            }
            if (!vowels.contains(bb)) {
                newBytes[j] = b;
                j--;
            }
            if (vowels.contains(aa) && vowels.contains(bb)) {
                newBytes[i] = b;
                newBytes[j] = a;
                i++;
                j--;
            }
        }
        return new String(newBytes);
    }

    /**
     * 345. Reverse Vowels of a String (Easy)
     * 该题答案
     *
     * @param s
     */
    public String reverseVowels2(String s) {
        if (s == null) return null;
        int i = 0, j = s.length() - 1;
        char[] result = new char[s.length()];
        while (i <= j) {
            char ci = s.charAt(i);
            char cj = s.charAt(j);
            if (!vowels.contains(ci)) {
                result[i++] = ci;
            } else if (!vowels.contains(cj)) {
                result[j--] = cj;
            } else {
                result[i++] = cj;
                result[j--] = ci;
            }
        }
        return new String(result);
    }

    /**
     * 4. 回文字符串
     * 680. Valid Palindrome II (Easy)
     * Leetcode / 力扣
     * Input: "abca"
     * Output: True
     * Explanation: You could delete the character 'c'.
     * 题目描述：可以删除一个字符，判断是否能构成回文字符串。
     *
     * @param s
     */
    public boolean validPalindrome(String s) {
        if (s == null) {
            return false;
        }
        char[] chars = new char[s.length()];
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return judgeDelStr(s, i++, j) || judgeDelStr(s, i, j--);
            }
        }
        return false;
    }

    public boolean judgeDelStr(String str, int a, int b) {
        while (a <= b) {
            if (str.charAt(a) != str.charAt(b)) {
                return false;
            }
            a++;
            b--;
        }
        return true;
    }

    /**
     * 5. 归并两个有序数组
     * 88. Merge Sorted Array (Easy)
     * Leetcode / 力扣
     * Input:
     * nums1 = [1,2,3,0,0,0], m = 3
     * nums2 = [2,5,6],       n = 3
     * <p>
     * Output: [1,2,2,3,5,6]
     * 题目描述：把归并结果存到第一个数组上。
     * <p>
     * <p>
     * 需要从尾开始遍历，否则在 nums1 上归并得到的值会覆盖还未进行归并比较的值。
     *
     * @param nums1
     * @param m
     * @param nums2
     * @param n
     */
    public int[] merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m - 1, index2 = n - 1;
        int indexMerge = m + n - 1;
        while (index1 >= 0 || index2 >= 0) {
            if (index1 < 0) {
                nums1[indexMerge--] = nums2[index2--];
            } else if (index2 < 0) {
                nums1[indexMerge--] = nums1[index1--];
            } else if (nums1[index1] > nums2[index2]) {
                nums1[indexMerge--] = nums1[index1--];
            } else {
                nums1[indexMerge--] = nums2[index2--];
            }
        }
        return nums1;
    }

    public int[] merge2(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] mergeInts = Arrays.copyOf(nums1, m + n);
        int index1 = m - 1;
        int index2 = n - 1;
        int indexMerge = m + n - 1;
        while (index1 >= 0 || index2 >= 0) {
            if (index1 < 0) {
                mergeInts[indexMerge] = nums2[index2];
                indexMerge--;
                index2--;
            } else if (index2 < 0) {
                mergeInts[indexMerge] = mergeInts[index1];
                indexMerge--;
                index1--;
            } else if (mergeInts[index1] > nums2[index2]) {
                mergeInts[indexMerge] = mergeInts[index1];
                indexMerge--;
                index1--;
            } else {
                mergeInts[indexMerge] = nums2[index2];
                indexMerge--;
                index2--;
            }
        }

        return mergeInts;
    }

    public int[] merge3(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] mergeInts = Arrays.copyOf(nums1, m + n);
        int index1 = m - 1;
        int index2 = n - 1;
        int indexMerge = m + n - 1;
        while (index1 >= 0 || index2 >= 0) {
            if (index1 < 0) {
                mergeInts[indexMerge--] = nums2[index2--];
            } else if (index2 < 0) {
                mergeInts[indexMerge--] = mergeInts[index1--];
            } else if (mergeInts[index1] > nums2[index2]) {
                mergeInts[indexMerge--] = mergeInts[index1--];
            } else {
                mergeInts[indexMerge--] = nums2[index2--];
            }
        }
        return mergeInts;
    }

    public int findKthLargest(int[] nums, int k) {
        // init heap 'the smallest element first'
        PriorityQueue<Integer> heap =
                new PriorityQueue<Integer>();

        //每次迭代保证堆中只存在K个元素，利用小顶堆的特性，大于k个元素，就将最小的值poll，迭代完毕后，留在堆顶的正是第K个最大元素。
        for (int n : nums) {
            heap.add(n);
            if (heap.size() > k)
                heap.poll();
        }
        // output
        return heap.poll();
    }


    public static void main(String[] args) {
        TwoPointers twoPointers = new TwoPointers();
        //167. Two Sum II - Input array is sorted (Easy)
        int[] numbers = {2, 7, 9, 10, 11, 15};
        int target = 21;
        int[] aws = twoPointers.twoSum(numbers, target);
        for (int index : aws) {
            System.out.println(index);
        }

        //633. Sum of Square Numbers (Easy)
        int target2 = 16;
        boolean judgeSquareSum = twoPointers.judgeSquareSum(target2);
        System.out.println(judgeSquareSum);

        //345. Reverse Vowels of a String (Easy)
//        String aaa = "qawteeyz";
//        String s = twoPointers.reverseVowels(aaa);
        String aaa = "leetcode";
        String s = twoPointers.reverseVowels(aaa);
        System.out.println("转换前：" + aaa + ", 转换后：" + s);
        System.out.println(vowels.contains('a') && vowels.contains('e'));

        //680. Valid Palindrome II (Easy)
        String test = "abcfdcba";
        boolean validPalindrome = twoPointers.validPalindrome(test);
        System.out.println(validPalindrome);

        //
        int[] nums1 = {1, 2, 3, 8, 9};
        int[] nums2 = {4, 5, 6};
        int[] mergeInts = twoPointers.merge3(nums1, nums2);

        for (int index : mergeInts) {
            System.out.print(index + ", ");
        }

        int[] nums = {2, 3, 5, 4, 1, 9, 6};
        int k = 2;
        int kthLargest = twoPointers.findKthLargest(nums, k);
        System.out.println(kthLargest);

    }


}
